using System;
using System.Collections.Generic;

namespace Ack
{
	public class Misc
	{
		public static byte[] TrimArray(byte[] input, int length)
		{
			byte[] trimmed = new byte[length];
			Array.ConstrainedCopy(input, 0, trimmed, 0, length);
			return trimmed;
		}
		
		public static byte[] TrimArray(byte[] input, int start, int length)
		{
			byte[] trimmed = new byte[length];
			Array.ConstrainedCopy(input, start, trimmed, 0, length);
			return trimmed;
		}
		
		public static byte[] InvertPattern(byte[] input, int start, int length)
		{
			byte[] output = new byte[length];
			for(int i = 0; i < length; ++i)
			{
				output[i] = (byte)~input[start+i];
			}
			return output;
		}
		
		public static byte[] EncodeRowRepeats(ulong pattern)
		{
			byte[] output = new byte[9];
			int len = 0;
			output[len++] = 0;
			output[len++] = (byte)(pattern & 0xFF);
			
			byte lastRow = output[1];
			for(int y = 1; y < 8; ++y)
			{
				byte row = (byte)((pattern >> 8*y) & 0xFF);
				
				if(row != lastRow)
				{
					output[len++] = row;
					output[0] |= (byte)(1 << (7-y));
				}
				
				lastRow = row;
			}
			
			return TrimArray(output,len);
		}

		public static int GetRowRepeatsByteCount(ulong pattern)
		{
			int len = 2;
			
			byte lastRow = (byte)((pattern >> 8*0) & 0xFF);
			for(int y = 1; y < 8; ++y)
			{
				byte row = (byte)((pattern >> 8*y) & 0xFF);
				
				if(row != lastRow)
				{
					len++;
				}
				
				lastRow = row;
			}
			
			return len;
		}		
		public static byte[] EncodeRCR(ulong pattern)
		{
			byte[] output = EncodeRowRepeats(pattern);
			byte[] outputT = EncodeRowRepeats(Transpose8x8(pattern));

			// Select the transpose if it take less bytes.
			// If so, also set bit 7 in the RCR header.
			if(outputT.Length < output.Length)
			{
				output = outputT;
				output[0] |= 0x80;
			}
			
			return output;
		}		

		public static int GetRCRByteCount(ulong pattern)
		{
			int rows = GetRowRepeatsByteCount(pattern);
			int columns = GetRowRepeatsByteCount(Transpose8x8(pattern));

			return Math.Min(rows,columns);
		}		
		
		public static ulong Transpose8x8(ulong pattern)
		{
			byte[] input = BitConverter.GetBytes(pattern);
			byte[] output = new byte[8];
			for(int y = 7; y >= 0; --y)
			{
				byte outRow = 0;
				outRow |= (byte)(((input[0] >> y) & 1) << 7);
				outRow |= (byte)(((input[1] >> y) & 1) << 6);
				outRow |= (byte)(((input[2] >> y) & 1) << 5);
				outRow |= (byte)(((input[3] >> y) & 1) << 4);
				outRow |= (byte)(((input[4] >> y) & 1) << 3);
				outRow |= (byte)(((input[5] >> y) & 1) << 2);
				outRow |= (byte)(((input[6] >> y) & 1) << 1);
				outRow |= (byte)(((input[7] >> y) & 1) << 0);
				output[7-y] = outRow;				
			}
			
			return BitConverter.ToUInt64(output,0);
		}		
		
		public static byte[] Transpose8x8(byte[] input, int patternIndex)
		{
			byte[] output = new byte[8];
			for(int y = 7; y >= 0; --y)
			{
				byte outRow = 0;
				outRow |= (byte)(((input[patternIndex*8+0] >> y) & 1) << 7);
				outRow |= (byte)(((input[patternIndex*8+1] >> y) & 1) << 6);
				outRow |= (byte)(((input[patternIndex*8+2] >> y) & 1) << 5);
				outRow |= (byte)(((input[patternIndex*8+3] >> y) & 1) << 4);
				outRow |= (byte)(((input[patternIndex*8+4] >> y) & 1) << 3);
				outRow |= (byte)(((input[patternIndex*8+5] >> y) & 1) << 2);
				outRow |= (byte)(((input[patternIndex*8+6] >> y) & 1) << 1);
				outRow |= (byte)(((input[patternIndex*8+7] >> y) & 1) << 0);
				output[7-y] = outRow;				
			}
			
			return output;
		}		
		
		public static ulong ExtractPattern(byte[] byteArray, int patternIndex)
		{
			return BitConverter.ToUInt64(TrimArray(byteArray, patternIndex * 8, 8), 0);
		}

		public static bool HasZeroByte(ulong ul)
		{
			return ((ul - 0x0101010101010101) & ~ul & 0x8080808080808080) != 0;
		}
		
		public static byte ReverseByte(byte b)
		{
			return (byte)(((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16); 
		}
		
		public static ulong ReversePatternX(ulong pattern)
		{
			ulong rx = 0;
			for(int pshift = 0; pshift < 64; pshift += 8)
			{
				rx |= ((ulong)Misc.ReverseByte((byte)(pattern >> pshift))) << pshift;
			}				
			return rx;
		}

		public static ulong ReversePatternY(ulong pattern)
		{
			ulong ry = 0;
			for(int pshift = 0, pshift2 = 56; pshift < 64; pshift += 8, pshift2 -= 8)
			{
				ry |= ((ulong)((pattern >> pshift) & 0xFF)) << pshift2;
			}
			return ry;
		}
		
		public static ulong ReversePatternXY(ulong pattern)
		{
			ulong first = pattern & 0xFFFFFFFFUL;
			ulong second = (pattern >> 32) & 0xFFFFFFFFUL;
			
			first = ((first >> 0x01) & 0x55555555UL) | ((first << 0x01) & 0xaaaaaaaaUL);
			first = ((first >> 0x02) & 0x33333333UL) | ((first << 0x02) & 0xccccccccUL);
			first = ((first >> 0x04) & 0x0f0f0f0fUL) | ((first << 0x04) & 0xf0f0f0f0UL);
			first = ((first >> 0x08) & 0x00ff00ffUL) | ((first << 0x08) & 0xff00ff00UL);
			first = ((first >> 0x10) & 0x0000ffffUL) | ((first << 0x10) & 0xffff0000UL);

			second = ((second >> 0x01) & 0x55555555UL) | ((second << 0x01) & 0xaaaaaaaaUL);
			second = ((second >> 0x02) & 0x33333333UL) | ((second << 0x02) & 0xccccccccUL);
			second = ((second >> 0x04) & 0x0f0f0f0fUL) | ((second << 0x04) & 0xf0f0f0f0UL);
			second = ((second >> 0x08) & 0x00ff00ffUL) | ((second << 0x08) & 0xff00ff00UL);
			second = ((second >> 0x10) & 0x0000ffffUL) | ((second << 0x10) & 0xffff0000UL);
			
			return (first << 32) + second;
		}		
		
		public int Log2(uint x)
		{
			return    ((x & 0xAAAAAAAAUL) != 0 ? 1:0)
					| ((x & 0xCCCCCCCCUL) != 0 ? 1:0) << 1
					| ((x & 0xF0F0F0F0UL) != 0 ? 1:0) << 2
					| ((x & 0xFF00FF00UL) != 0 ? 1:0) << 3
					| ((x & 0xFFFF0000UL) != 0 ? 1:0) << 4;
		}
				
		public bool IsPow2(uint x)
		{
			return (x & (x - 1)) == 0;
		}		
	}
}
